iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 28
0
Software Development

One Punch 一拳搞定前後端面試系列 第 28

[One Punch 一拳搞定前後端面試] DAY-28 - Bubble Sort

  • 分享至 

  • xImage
  •  

Bubble Sort

給一個裡面都是整數的陣列,請由小到大排列,回傳新的陣列。

Bubble Sort 又稱氣泡排序法,最簡單的排序法,但並不是最有效率的。

後面兩篇我們會介紹其他排序方法,即討論其差別。

本文同時發布於好讀整理版

想法

一個一個遍歷,大的數字往右邊移動,遍歷完一次後少算一個,繼續遍歷直到結束。

實作

JavaScript 實作

function bubbleSort(ary) {
  for (let i = 0; i < ary.length; i++) {
    for (let j = 0; j < ary.length - i - 1; j++) {
      if (ary[j] > ary[j + 1]) {
        const smaller = ary[j + 1]
        ary[j + 1] = ary[j] // 大的往右邊移動一格
        ary[j] = smaller // 小的補上左邊
      }
    }
  }

  return ary
}

說明:

  • 第二層迴圈 -1 是因為 index 從 0 開始,所以長度 -1 才會是最後一個數的 index。
  • -i 是因為最大的數已經在最右邊了,所以可以少算 i 次。ex:第一圈 0,第二圈因為已經最大的數在最右邊了所以 -1 次。

Java 實作

一樣意思,沒有差很多。

static void bubbleSort(int[] arr) {
int n = arr.length;
int smaller = 0;

for(int i=0; i < n; i++){
  for(int j=1; j < (n-i); j++){
    if(arr[j-1] > arr[j]){
        smaller = arr[j-1];
        arr[j-1] = arr[j];
        arr[j] = smaller;
      }
    }
  }
}

本篇是我們介紹的第一種排序法,後面兩篇會介紹其他兩種

敬請期待!

本文同時發布於好讀整理版


上一篇
[One Punch 一拳搞定前後端面試] DAY-27 -Binary Search Tree - Contains
下一篇
[One Punch 一拳搞定前後端面試] DAY-29 - Selection Sort
系列文
One Punch 一拳搞定前後端面試30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言